package Array.easy;

import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

/**
 * 1. 问题描述
 *      给定一个整数数组和一个整数k，判断数组中是否存在两个不同的索引i和j，
 *      使得nums [i] = nums [j]，并且 i 和 j的差的 绝对值 至多为 k。
 *
 * 2， 算法分析
 *      本题实际上是一个关于滑动窗口的算法题目，但是由于使用不同的数据结构进行窗口的维护，
 *      所带来的效率也会不同，下面我们一一分析到底该使用哪一种数据结构来维护窗口
 *
 *      1. 最简单的穷举法(不在赘述)
 *
 *      由于在算法种我们需要大量的查询操作，所以我们可能会考虑树结构查询例如平衡二叉查询树(BST)
 *      此时我们的查询从线性转化为log级别的，或者使用散列表，其查询的效率为O(1)
 *      1. 使用TreeSet作为窗口的维护
 *
 *      2. 使用hashSet作为窗口的维护
 *
 *      无论使用上述哪一种，代码基本上一样，但是效率却相差甚远，前者是O(nlogn)级别，后者是O(n)
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 存在重复元素2 {
    public static void main(String[] args) {

    }

    /**
     * 1. 穷举法
     * @param nums
     * @param k
     * @return
     */
    public static boolean containsNearbyDuplicate(int[] nums, int k) {
        if (k <= 0 || nums == null) {return false;}
        int len = nums.length;
        for (int i = 1; i <= k; i++) { // 控制索引差
            // 当前索引差为i
            for (int j = 0; j+i < len; j++) {
                if (nums[j] == nums[j+i]) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * TreeSet维护窗口
     * 如果当前元素不在窗口内，将该当前元素滑入窗口内部，如果当前已经存在，直接返回true
     * 如果当前滑进窗口的元素使得窗口的长度大于k，为了维护窗口的大小始终保持在k，所以从
     * 窗口种剪掉nums[k-i]元素，i代表当前元素在nums中的索引
     * @param nums
     * @param k
     * @return
     */
    public static boolean containsNearbyDuplicate2(int[] nums, int k) {
        if (k <= 0 || nums == null) {return false;}
        Set<Integer> set = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                return true;
            } else {
                set.add(nums[i]);
            }
            if (set.size() > k) {
                set.remove(nums[k-i]);
            }
        }
        return false;
    }

    public static boolean containsNearbyDuplicate3(int[] nums, int k) {
        if (k <= 0 || nums == null) {return false;}
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                return true;
            } else {
                set.add(nums[i]);
            }
            if (set.size() > k) {
                set.remove(nums[k-i]);
            }
        }
        return false;
    }
}
